
// 322.零钱兑换
class Solution {
public:
    int coinChange(vector<int>& nums, int amount) {
        // 完全背包问题
        const int INF = 0x3f3f3f3f;
        int n = nums.size();
        vector<int> dp(amount + 1 , INF);   // 每个位置表示恰好能达到该金额的最小硬币数量
        dp[0] = 0;
        for(int i = 1 ; i <= n ;i++)
            for(int j = nums[i - 1] ; j <= amount ; j++)
                dp[j] = min(dp[j] , dp[j - nums[i - 1]] + 1);
                
        return dp[amount] == INF ? -1 : dp[amount];
    }
};